1. Field of the Invention
The present invention relates to a method of error correction and signal detection, and more particularly to, a method of generating parity data based on low-density parity check matrices and an apparatus therefor.
2. Description of the Related Art
A conventional coding method based on Low Density Parity Check (LDPC) codes for error correction generates parity check codes that have a predetermined number of elements having a value of one in rows and columns of the parity check codes, and then generates parity data based on the parity check codes.
That is, in the coding method based on the LDPC codes, a parity check matrix H having a predetermined number of elements having a value of one in its rows and columns is formed, and a codeword x satisfying the equation Hx=0 is obtained.
The codeword x includes original data and parity data.
In order to obtain the parity data, the parity check matrix H is converted into a generator matrix G by Gaussian elimination, or into a lower triangular form. Since the generator matrix G is no longer a sparse matrix, increased computational time is required for calculating the codeword x.
A conventional parity check code matrix H of the form
         [                            A                          B                          T                                      C                          D                          E                      ]  is shown in FIG. 1.
To obtain the codeword x satisfying the equation Hx=0, triangulation of the parity check code matrix H is performed, and then pre-multiplication using Gaussian elimination is carried out, as shown in the following equation (1).
                                          [                                                            I                                                  0                                                                                                  -                                          ET                                              -                        1                                                                                                              I                                                      ]                    ⁡                      [                                                            A                                                  B                                                  T                                                                              C                                                  D                                                  E                                                      ]                          =                  [                                                    A                                            B                                            T                                                                                      -                                      ET                                          -                      1                                                                                                                    A                  +                  C                  -                                                            ET                                              -                        1                                                              ⁢                    B                                    +                  D                                                            0                                              ]                                    (        1        )            
However, the above calculation process is highly complex and time consuming.
The basic concept of the LDPC is described by D. J. Mackay, in “Good Error-Correction Codes Based on Very Sparse Matrices”, IEEE Trans. on Information Theory, vol. 45, No. 2, pp. 399-431, 1999, and a conventional implementation of the H matrix is presented by T. Richardson and R. Urbanke in “Efficient Encoding of Low-Density Parity-Check Codes”, IEEE Trans. on Information Theory, vol. 47, No. 2, pp. 638-656, 2001.